package syf.graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Graph {
    private final int[][] adjacent;//记录连接表
    private List<String> listNode;//记录节点
    private final boolean[] isVisited; //记录某个结点是否被访问
    List<Integer> count;//记录队列
    public static void main(String[] args) {
//        String[] nodes={"A","B","C","D","E"};
        String nodes[] = {"1", "2", "3", "4", "5", "6", "7", "8"};
        Graph graph=new Graph(nodes.length);
        for (int i=0;i<nodes.length;i++)
            graph.insertNode(nodes[i]);
//        graph.insertBound(0,1,1);
//        graph.insertBound(0,2,1);
//        graph.insertBound(2,1,1);
//        graph.insertBound(0,1,1);
//        graph.insertBound(1,3,1);
//        graph.insertBound(1,4,1);

        graph.insertBound(0, 1, 1);
        graph.insertBound(0, 2, 1);
        graph.insertBound(1, 3, 1);
        graph.insertBound(1, 4, 1);
        graph.insertBound(3, 7, 1);
        graph.insertBound(4, 7, 1);
        graph.insertBound(2, 5, 1);
        graph.insertBound(2, 6, 1);
        graph.insertBound(5, 6, 1);
        graph.showAll();
        int index=4;
        int next = graph.getNext(index);
        System.out.println(next);
        int nestToNode = graph.getNestToNode(index,next);
        System.out.println(nestToNode);

        //测试 深度优先
        graph.dfs();
        System.out.println("广度优先");
        //广度优先
//        graph.bsf();
    }
    //初始化图
    public  Graph(int n) {
        adjacent=new int[n][n];
        listNode= new ArrayList<>(n);
        isVisited=new boolean[n];
        count=new ArrayList<>();
    }
    //插入结点
    public void insertNode(String node){
        listNode.add(node);
    }
    //插入边界
    /**
     * 功能：添加边界，无向图的话正反都要加
     * @param r 行
     * @param l 列
     * @param weight 权值
     */
    public void insertBound(int r,int l,int weight){
        adjacent[r][l]=weight;
        adjacent[l][r]=weight;
    }
    //得到结点个数
    public int getSize(){
        return listNode.size();
    }
    //得到两点之间的边界权值
    public int getBoundWeight(int r,int l){
        return adjacent[r][l];
    }
    //遍历所有边界
    public void showAll(){
        for (int[] x:adjacent){
            System.err.println(Arrays.toString(x));
        }
    }
    //重载
    public void dfs(){
        for (int i=0;i<getSize();i++){
            if (!isVisited[i]){
                dfs(i);
            }
        }
    }
    //dfs深度优先遍历 访问过就标记为true
    private void dfs(int index){
        if (index<getSize()){
            System.out.print(listNode.get(index)+"->");
            isVisited[index]=true;
            int next=getNext(index);
            while (next!=-1){
                if (!isVisited[next]){//没访问过
                    {
                        dfs(next);
                    }
                }//可能第一条路的临街结点跑不通,就换下一个临街结点继续进行
                next=getNestToNode(index,next);
            }

        }
    }
    /**
     * 功能：得到要访问的结点的临街结点
     * @param index 第一个要访问的结点
     * @return 临街结点
     */
    public int getNext(int index){
        if (index>getSize()-1) {
            System.out.println("长度错误");
            return -1;
        }
        for (int i=0;i<getSize();i++){
            if (adjacent[index][i]==1){//说明找到了
                return i;
            }
        }//遍历完了都没找到则返回-1
        return -1;
    }
    /**
     * 得到要访问结点的临街结点的右边一节点
     * @param last 上一个进行查找的索引
     * @param j 上一个临街结点的下标
     * @return 上一个临街结点的右边结点
     * */
    public int getNestToNode(int last,int j){
        for (int i=j+1;i<getSize();i++){
            if (adjacent[last][i]==1) {
                return i;
            }
        }
        return -1;
    }
    /************************************************************************************************************/
    //广度优先
    public void bsf(){
        for (int i=0;i<getSize();i++){
            if (!isVisited[i]){
                bsf(i);
            }
        }
    }
    private void bsf(int index){
        System.out.print(listNode.get(index)+"->");
        count.add(index);
        isVisited[index]=true;
        while (count!=null){
           for (int i=0;i<getSize();i++){
               if (!isVisited[i]){//如果没有访问
                   if (adjacent[count.get(0)][i]==1){
                       isVisited[i]=true;
                       count.add(i);
                       System.out.print(listNode.get(i)+"->");
                   }
               }//一次就走完了
               if (count.size()==getSize())
                   break;
           }//没遍历完
           count.remove(0);
           if (count.size()==0)
               count=null;
        }
    }
}
